import math
n=12
def numSquares(n):
    squareList=[]
    for i in range(1,n):
        if int(math.sqrt(i))*int(math.sqrt(i))==i:
            squareList.append(i)
    print(squareList)
    #创建状态转移方程
    dp=[[0 for _ in range(n+1)] for _ in range(len(squareList))]
    #处理第一行
    for i in range(n+1):
        dp[0][i]=int(i/squareList[0])
    #处理剩余行
    for i in range(1,len(squareList)):
        for j in range(n+1):
            if j<squareList[i]:
                #无法选择当前值时
                #选0个当前值
                dp[i][j]=dp[i-1][j]
            else:
                #能选取多少个当前值
                maxNum=int(j/squareList[i])
                dp[i][j]=min(dp[i-1][j-maxNum*squareList[i]]+maxNum,dp[i-1][j])
    print(dp[len(squareList)-1][n])
numSquares(n)
